package sort;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {

    public static void heapSort(int[] nums) {
        //1. 调整堆为大顶堆
        initHeap(nums);
        //2. 依次选择最大值并调整
        for (int j = nums.length - 1; j >= 0; j--) {
            int tmp = nums[j];
            nums[j] = nums[0];
            nums[0] = tmp;
            adjustHeap(nums, 0, j);
        }
        Arrays.stream(nums).forEach(num -> {
            System.out.print(num + ",");
        });
    }

    /**
     * 初始化堆，用于第一次创建堆结构
     *
     * @param nums
     */
    private static void initHeap(int[] nums) {
        int beginIdx = (nums.length - 1) / 2;
        //从beginIdx开始依次遍历，直到根节点
        for (int i = beginIdx; i >= 0; i--) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            if (right >= nums.length) {//只有左节点
                if (nums[left] > nums[i]) {
                    swapNode(nums, left, i);
                }
            } else {//左右节点都存在
                if (nums[left] > nums[right]) {
                    if (nums[left] > nums[i]) {
                        swapNode(nums, left, i);
                    }
                } else {
                    if (nums[right] > nums[i]) {
                        swapNode(nums, right, i);
                    }
                }
            }
        }
    }

    private static void swapNode(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    /**
     * 调整堆，用于在每次排序后，将根节点重建为堆结构
     *
     * @param nums
     * @param len
     */
    private static void adjustHeap(int[] nums, int idx, int len) {
        int left = idx * 2 + 1;
        int right = idx * 2 + 2;
        if (left >= len) {
            return;
        }
        if (right >= len) {//只有左子树
            if (nums[left] > nums[idx]) {
                swapNode(nums, left, idx);
            }
        } else {// 左右子树都有
            if (nums[left] > nums[right]) {
                if (nums[left] > nums[idx]) {
                    swapNode(nums, left, idx);
                    adjustHeap(nums, left, len);
                }
            } else {
                if (nums[right] > nums[idx]) {
                    swapNode(nums, right, idx);
                    adjustHeap(nums, right, len);
                }
            }
        }
    }


    public static void main(String[] args) {
        HeapSort.heapSort(new int[]{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7});
    }
}
